/*	Program P12-3 Delete vertex.

    Brooks/Cole Publishing Company
	An International Thomson Publishing Company
	Copyright 1998. All Rights Reserved
*/

/*	==================== deleteVertex ====================
	Deletes an existing vertex only if its degree is 0.
	   Pre    dltKey is the key of the vertex to be deleted
	   Post   vertex deleted if degree 0
	          -or- an error code is returned
	   Return success +1 if successful
	                  -1 if degree not 0
	                  -2 if dltKey not found
*/

template <class TYPE, class KTYPE> 
int  Graph<TYPE, KTYPE> ::  deleteVertex (KTYPE dltKey)
{
//	Local Definitions 
	Vertex<TYPE>  *predPtr;
	Vertex<TYPE>  *walkPtr;

// Statements 
	if (!first)
	    return -2;

	// Locate vertex to be deleted 
	predPtr = NULL;
	walkPtr = first;
	while (walkPtr && dltKey > (walkPtr->data).key)
	   {
	    predPtr = walkPtr;
	    walkPtr = walkPtr->pNextVertex;
	   } // walkPtr && 
	if (!walkPtr || dltKey != (walkPtr->data.key))
	   return -2;
	   
	// Found vertex. Test degree. 
	if ((walkPtr->inDegree > 0) || (walkPtr->outDegree > 0))
	    return -1;
	
	// Okay to delete 
	if (!predPtr)
	    first = walkPtr->pNextVertex;
	else
	    predPtr->pNextVertex = walkPtr->pNextVertex;
	count--;
	delete walkPtr;
	return 1;
}  // deleteVertex 
